package org.lql.algo.codecrush.hot100.binaryTree;

import org.lql.algo.common.TreeNode;

/**
 * @author: liangqinglong
 * @date: 2025-09-07 16:44
 * @description: 543. 二叉树的直径 <a href="https://leetcode.cn/problems/diameter-of-binary-tree/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 **/
public class DiameterOfBinaryTree {

	int diameter;

	public int diameterOfBinaryTree(TreeNode root) {
		calculateDepth(root);
		return diameter;
	}

	private int calculateDepth(TreeNode node) {
		if (node == null) {
			return 0;
		}
		int leftDepth = calculateDepth(node.left);
		int rightDepth = calculateDepth(node.right);

		// 更新全局最大直径，可能经过当前节点或不经过当前节点
		diameter = Math.max(diameter, leftDepth + rightDepth);

		// 返回节点深度
		return Math.max(leftDepth, rightDepth) + 1;
	}
}
